package com.linyaonan.leetcode.medium._17;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }
        return buildAllCom(digits);
    }

    private List<String> buildAllCom(String org) {
        StringBuilder sb = new StringBuilder();
        List<String> result = new ArrayList<>();
        String[][] save = new String[][]{{"a","b","c"},{"d","e","f"},{"g","h","i"},{"j","k","l"},{"m","n","o"},{"p","q","r","s"},{"t","u","v"},{"w","x","y","z"}};
        bt(sb, 0, save, org, result);
        return result;
    }

    /**
     * 与全排列问题类似，都是使用回溯算法处理
     * @param sb
     * @param count
     * @param charFromNum
     * @param org
     * @param resultList
     */
    private void bt(StringBuilder sb, int count, String[][] charFromNum, String org, List<String> resultList) {
        if (count == org.length()) {
            resultList.add(sb.toString());
        } else {
            String[] strings = charFromNum[org.charAt(count) - '2'];
            for (String string : strings) {
                sb.append(string);
                bt(sb, count + 1, charFromNum, org, resultList);
                sb.deleteCharAt(count);
            }
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        List<String> strings = s.letterCombinations("235");
        System.out.println(strings);
    }
}